package leetcode.code;

import leetcode.helper.tree.TreeNode;

public class Solution112 {
	public boolean hasPathSum(TreeNode root, int targetSum) {
		if ((root == null) || (root.left == null && root.right == null))
			return false;
		return hasPathSum(root, targetSum, 0);
	}

	private boolean hasPathSum(TreeNode root, int targetSum, int sum) {
		if (root.left == null && root.right == null) {
			if (sum + root.val == targetSum)
				return true;
			else
				return false;
		}
		if (root.left != null) {
			boolean left = this.hasPathSum(root.left, targetSum, sum + root.val);
			if (left)
				return true;
		}
		if (root.right != null) {
			boolean right = this.hasPathSum(root.right, targetSum, sum + root.val);
			if (right)
				return true;
		}
		return false;
	}
}
